#include "main/utils.h"
using namespace std;

map<string, map<string, double>> buildGraph(const vector<vector<string>>& equations,
                                            const vector<double>& values) {
  map<string, map<string, double>> graph;
  for (int i = 0; i < equations.size(); ++i) {
    string from = equations[i][0];
    string to = equations[i][1];
    
    graph[from][to] = values[i];
    graph[to][from] = 1.0 / values[i];
  }
  return graph;
}

double calc(string from, string to,
            map<string, map<string, double>> graph,
            set<string> visited) {
  if (from == to) {
    return 1.0;
  }
  visited.insert(from);
  for (auto next : graph[from]) {
    if (visited.find(next.first) == visited.end()) {
      double next_val = calc(next.first, to, graph, visited);
      if (next_val > 0) {
        return next_val * next.second;
      }
    }
  }
  visited.erase(from);
  return -1;
}

vector<double> calcEquation(const vector<vector<string>>& equations,
                            const vector<double> values,
                            const vector<vector<string>> queries) {
  auto graph = buildGraph(equations, values);
  vector<double> result;
  for (int i = 0; i < queries.size(); ++i) {
    auto from = queries[i][0];
    auto to = queries[i][1];
    if (graph.find(from) == graph.end() ||
        graph.find(to) == graph.end()) {
      result.push_back(-1);
    } else {
      set<string> visited;
      result.push_back(calc(from, to, graph, visited));
    }
  }
  return result;
}

int main() {
  vector<vector<string>> equations = {{"a", "b"}, {"b", "c"}};
  vector<double> values = {2.0, 3.0};
  vector<vector<string>> queries = {{"a", "c"}, {"b", "a"}, {"a", "e"}, {"a", "a"}, {"x", "x"}};
  auto result = calcEquation(equations, values, queries);
  printVec("o111", result);

  return 0;
}
